#include "DGraphUtil.h"

// implement tarjan's algorithm to find Strongly Connected Component from a given start node
void DGraphUtil::tarjan(DGraph& g, int vid, int& index, /*hash_map*/map<int,
		pair<int, int> >& order, vector<int>& sn, multimap<int, int>& sccmap,
		int& scc) {
	order[vid].first = index;
	order[vid].second = index;
	index++;
	sn.push_back(vid);
	g[vid]._visited = true;
	EdgeList el = g.edges_from(vid);
	EdgeList::iterator eit;
	for (eit = el.begin(); eit != el.end(); eit++) {
		if (!g[*eit]._visited) {
			tarjan(g, *eit, index, order, sn, sccmap, scc);
			order[vid].second = min(order[*eit].second, order[vid].second);
		} else if (find(sn.begin(), sn.end(), (*eit)) != sn.end()) {
			order[vid].second = min(order[*eit].first, order[vid].second);
		}
	}

	if (order[vid].first == order[vid].second) {
		vector<int>::reverse_iterator rit;
		for (rit = sn.rbegin(); rit != sn.rend(); rit++) {
			if ((*rit) != vid) {
				sccmap.insert(make_pair(scc, *rit));
				//	sccmap[*rit] = scc;
				sn.pop_back();
			} else {
				sccmap.insert(make_pair(scc, *rit));
				//	sccmap[*rit] = scc;
				sn.pop_back();
				break;
			}
		}
		scc++;
	}
}

// merge Strongly Connected Component
// return vertex map between old vertex and corresponding new merged vertex
void DGraphUtil::merge_SCC(DGraph& g, int* on, vector<int>& reverse_topo_sort) {
	vector<int> sn;
	/*hash_map*/
	map<int, pair<int, int> > order;
	int ind = 0;
	multimap<int, int> sccmap; // each vertex id correspond with a scc num
	int scc = 0;
	int vid;
	int origsize = g.number_of_vertices();

	for (int i = 0; i < origsize; i++) {
		vid = i;
		if (g[vid]._visited)
			continue;
		tarjan(g, vid, ind, order, sn, sccmap, scc);
	}
	// no component need to merge
	if (scc == origsize) {
		for (int i = 0; i < origsize; i++) {
			on[i] = i;
		}
		// topological sort
		topological_sort(g, reverse_topo_sort);
		// update graph's topological id
		for (int i = 0; i < reverse_topo_sort.size(); i++) {
			g[reverse_topo_sort[i]]._TopoID = reverse_topo_sort.size() - i - 1;
		}
		return;
	}

	/*hash_map*/
	map<int, vector<int> > inlist, outlist;
	g.extract(inlist, outlist);

	multimap<int, int>::iterator mit;
	mit = sccmap.begin();
	int num_comp;
	int maxid = g.number_of_vertices() - 1;
	while (mit != sccmap.end()) {
		num_comp = mit->first;

		if (++sccmap.lower_bound(num_comp) == sccmap.upper_bound(num_comp)) {
			on[mit->second] = mit->second;
			++mit;
			continue;
		}

		maxid++;
		inlist[maxid] = vector<int> ();
		outlist[maxid] = vector<int> ();

		for (; mit != sccmap.upper_bound(num_comp); ++mit) {
			on[mit->second] = maxid;

			vector<int> vec = inlist[mit->second];
			vector<int>::iterator vit, vit1;
			vector<int> vec1;
			bool hasEdge = false;

			// copy all incoming edges
			for (vit = vec.begin(); vit != vec.end(); vit++) {
				hasEdge = false;
				vec1 = outlist[*vit];
				for (vit1 = vec1.begin(); vit1 != vec1.end(); vit1++) {
					if (*vit1 == maxid) {
						hasEdge = true;
						break;
					}
				}
				if (!hasEdge && (*vit != maxid)) {
					inlist[maxid].push_back(*vit);
					outlist[*vit].push_back(maxid);
				}
			}

			// copy all outgoing edges
			vec = outlist[mit->second];
			for (vit = vec.begin(); vit != vec.end(); vit++) {
				hasEdge = false;
				vec1 = inlist[*vit];
				for (vit1 = vec1.begin(); vit1 != vec1.end(); vit1++)
					if (*vit1 == maxid) {
						hasEdge = true;
						break;
					}
				if (!hasEdge && (*vit != maxid)) {
					outlist[maxid].push_back(*vit);
					inlist[*vit].push_back(maxid);
				}
			}

			// delete old vertex
			vec = inlist[mit->second];
			for (vit = vec.begin(); vit != vec.end(); vit++) {
				for (vit1 = outlist[*vit].begin(); vit1 != outlist[*vit].end();) {
					if (*vit1 == mit->second)
						outlist[*vit].erase(vit1);
					else
						vit1++;
				}
			}
			vec = outlist[mit->second];
			for (vit = vec.begin(); vit != vec.end(); vit++) {
				for (vit1 = inlist[*vit].begin(); vit1 != inlist[*vit].end();) {
					if (*vit1 == mit->second)
						inlist[*vit].erase(vit1);
					else
						vit1++;
				}
			}
			outlist.erase(mit->second);
			inlist.erase(mit->second);
		}
	}

	g = DGraph(inlist, outlist);

	// topological sort
	topological_sort(g, reverse_topo_sort);
	// update graph's topological id
	for (int i = 0; i < reverse_topo_sort.size(); i++)
		g[reverse_topo_sort[i]]._TopoID = reverse_topo_sort.size() - i - 1;

	// update index map
	/*hash_map*/
	map<int, int> indexmap;
	/*hash_map*/
	map<int, vector<int> >::iterator hit;
	int k;
	for (hit = outlist.begin(), k = 0; hit != outlist.end(); hit++, k++) {
		indexmap[hit->first] = k;
	}
	for (k = 0; k < origsize; k++) {
		on[k] = indexmap[on[k]];
	}

	/*
	 cout << "Index Map" << endl;
	 for (int i = 0; i < origsize; i++)
	 cout << on[i] << " ";
	 cout << endl;
	 cout << "roots: " << g.getRoots().size() << endl;
	 */
}

// depth first search given a start node
void DGraphUtil::dfs(DGraph& g, int vid, vector<int>& preorder,
		vector<int>& postorder, vector<bool>& visited) {
	visited[vid] = true;
	preorder.push_back(vid);
	EdgeList el = g.edges_from(vid);
	EdgeList::iterator eit;
	int nextid = -1;
	// check whether all child nodes are visited
	for (eit = el.begin(); eit != el.end(); eit++) {
		if (!visited[*eit]) {
			nextid = *eit;
			dfs(g, nextid, preorder, postorder, visited);
		}
	}
	postorder.push_back(vid);
}

/// topological sorting by depth-first search
/// return reverse order of topological_sorting list
void DGraphUtil::topological_sort(DGraph& g, vector<int>& rts) {
	vector<bool> visited(g.number_of_vertices(), false);
	vector<int> preorder;
	vector<int> postorder;
	vector<int> roots = g.get_roots();
	vector<int>::iterator sit;
	// depth-first-search whole DGraph
	for (sit = roots.begin(); sit != roots.end(); sit++) {
		if (!visited[*sit])
			dfs(g, (*sit), preorder, postorder, visited);
	}

	rts = postorder;

	// for test
	/*
	 cout << "Topo sorting(DGraphUtil): ";
	 vector<int>::iterator vit;
	 for (vit = ts.begin(); vit != ts.end(); vit++)
	 cout << (*vit) << " ";
	 cout << endl;
	 */
}

/// compute transitive closure
/// from Klaus Simon's paper "An improved algorithm for transitive closure on acyclic diDGraphs"
void DGraphUtil::transitive_closure(DGraph& g, DGraph& tc) {
	vector<int> ts;
	vector<int>::iterator vit;
	topological_sort(g, ts);

	EdgeList el;
	EdgeList::iterator eit;
	map<int, set<int> > ms;
	map<int, set<int> >::iterator mit;
	set<int>::iterator sit;
	// build set map iteratively
	// using reverse order of topological_sort list
	for (vit = ts.begin(); vit != ts.end(); vit++) {
		set<int> s;
		s.insert(*vit);
		ms[*vit] = s;
		el = g.edges_from(*vit);
		for (eit = el.begin(); eit != el.end(); eit++) {
			ms[*vit].insert(ms[*eit].begin(), ms[*eit].end());
		}
	}

	// add edges based on edge map
	for (mit = ms.begin(); mit != ms.end(); mit++) {
		set<int> s = (*mit).second;
		int src = (*mit).first;
		for (sit = s.begin(); sit != s.end(); sit++) {
			tc.add_edge(src, (*sit));
		}
	}
}

/// Add reachable pairs to tcm
void DGraphUtil::transitive_closure_matrix(DGraph& g,
		map<pair<int, int> , bool> &tcm) {
	//#ifdef _TEST_
	DGraph tc(g.number_of_vertices());
	DGraphUtil::transitive_closure(g, tc);
	EdgeList el;
	EdgeList::iterator eit;
	for (int i = 0; i < tc.number_of_vertices(); i++) {
		el = tc.edges_from(i);
		for (eit = el.begin(); eit != el.end(); eit++) {
			tcm[make_pair(i, *eit)] = true;
		}
	}
	//#endif
	//cout << tcm.size() << endl;
}

// finding part fo spanning tree of the original graph by dfs from a certain vertex v
int DGraphUtil::rightmost_spanning_tree2(int v, vector<bool>& visited,
		DGraph& graph, DTree& tree, int& post_order, int& level, hash_map<int,
				int>& pre_order_save, int& pre) {
	visited[v] = true;
	//	graph[v].level = level;

	bool first = true;
	int supPreN=-1;
	int tempPreN=-1;

	pre_order_save[v] = pre++;
	int min_level = level;

	int i = 0;
	EdgeList outEdges = graph.edges_from(v);
	//  for (EdgeList::reverse_iterator eit=outEdges.rbegin(); eit!=outEdges.rend(); ++eit)
	for (EdgeList::iterator eit = outEdges.begin(); eit != outEdges.end(); ++eit) // modified on Dec 19, 201
	{

		int adjV = *eit; // id of vertext adjacent to vid
		if (visited[adjV] == false) {
			//			graph[v].level = level;
			if (!first) {
				level++;
			}


			tree.add_edge(v, adjV);
			tempPreN=rightmost_spanning_tree2(adjV, visited, graph, tree, //NTE,
					post_order, level, pre_order_save, pre);

			if(first)
				supPreN=tempPreN;

			first = false;
			i++;
		} else {
			if (pre_order_save[v] > pre_order_save[adjV]) {
				if (min_level == graph[adjV].level + 1) {
					graph._shortNTE[v].push_back(adjV);
				} else{
					graph._longNTE[v].push_back(adjV);
					graph.lnte_nodes.insert(v);
					graph.lnte_nodes.insert(adjV);
				}
			}

		}
	}



	graph[v]._PreN = graph.number_of_vertices() - post_order;
	if(supPreN==-1)
		graph[v]._SupPreN=graph[v]._PreN;
	else
		graph[v]._SupPreN=supPreN;

	graph[v].level = level;

	post_order++;

	return graph[v]._SupPreN;
}

void DGraphUtil::rightmost_spanning_tree(DGraph& graph, DTree& tree) {
	tree.clear();
	//nonForest.clear();
	//  cout << graph.number_of_vertices() << endl;
	for (int v = 0; v < graph.number_of_vertices(); ++v) {
		tree.add_vertex(v);
		//nonForest.add_vertex();
	}

	vector<int> roots = graph.get_roots();
	vector<bool> visited(graph.number_of_vertices(), false);

	int post_order = 0;
	int level = 0;
	hash_map<int, int> pre_order_save;
	int pre = 0;
	for (vector<int>::iterator rit = roots.begin(); rit != roots.end(); ++rit) {
		//	graph[*rit].level=level;
		tree.addRoots(*rit);
		rightmost_spanning_tree2(*rit, visited, graph, tree, post_order, level,
				pre_order_save, pre);
		level++;
	}
}

bool compare1(const pair<int, int> t1, const pair<int, int> t2) {
	return (t1).second > (t2).second;
}

bool compare2(const pair<int, int> t1, const pair<int, int> t2) {
	return (t1).second < (t2).second;
}

//0. top 1. top+desc_compare1 2. top+desc_compare2 3.top+ancestor_compare1 4. top+ancestor_compare2
void DGraphUtil::opt_topological_sort(DGraph& g,
		vector<int> &reverse_topo_sort, int opt) {
	vector<bool> visited(g.number_of_vertices(), false);
	hash_map<int, int> opt_order;
	int order = g.number_of_vertices();
	int degrees[g.number_of_vertices()];
	int desc[g.number_of_vertices()];
	memset(desc, 0, g.number_of_vertices());
	memset(degrees, 0, g.number_of_vertices());

	queue<int> roots = g.init_roots_degrees(degrees);
	vector<int>::iterator sit;
	if (opt == 3 || opt == 4) {
		computePred(g, reverse_topo_sort, desc);
	}
//
//	if(opt==5){
//
//	}

	while (!roots.empty()) {

		int vid = roots.front();
		opt_order[vid] = order--;
		roots.pop();
		vector<pair<int, int> > temp;

		EdgeList el = g.edges_to(vid);
		EdgeList::iterator eit;

		for (eit = el.begin(); eit != el.end(); eit++) {
			if (opt == 1 || opt == 2)
				desc[*eit] += desc[vid] + 1;

			degrees[*eit]--;
			if (degrees[*eit] == 0) {

				if (opt != 0) {
					pair<int, int> node(*eit, desc[*eit]);
					temp.push_back(node);
				} else
					roots.push(*eit);
				//				else
				//					opt_order[*eit] = order--;
			}
		}
		if (opt != 0) {
			if (opt == 1 || opt == 3)
				sort(temp.begin(), temp.end(), compare1);
			else
				sort(temp.begin(), temp.end(), compare2);

			vector<pair<int, int> >::iterator id;
			for (id = temp.begin(); id != temp.end(); id++) {
				roots.push((*id).first);
			}
		}

	}

	g.rearrange(opt_order);
}

void DGraphUtil::computePred(DGraph& g, vector<int> &reverse_topo_sort,
		int* numPreds) {

	set<int> preds[g.number_of_vertices()];

	vector<int>::reverse_iterator i;
	for (i = reverse_topo_sort.rbegin(); i != reverse_topo_sort.rend(); i++) {
		EdgeList in = g.edges_to(*i);
		EdgeList::iterator edge;
		for (edge = in.begin(); edge != in.end(); edge++) {
//			numPreds[*i]=nu
			preds[*i].insert(preds[*edge].begin(), preds[*edge].end());
		}
		numPreds[*i] = preds[*i].size();

	}

}
